/**
 * 面试题53-2：0~n-1 中缺失的数字
 */
public class Offer_53_II {
    /**
     * 方法二：二分查找
     * <p>
     * 找到第一个 {@code nums[i] != i} 的索引即可
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     */
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 方法一：线性扫描
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int missingNumber1(int[] nums) {
        int i = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return i;
    }
}
